\documentclass{ctexart}
\usepackage{diagbox}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{geometry}
\usepackage{framed}
\usepackage{color}
\usepackage{subfigure}
\usepackage{array,tabularx}
\definecolor{shadecolor}{rgb}{0.92,0.92,0.92}

\title{二叉搜索树排序的实现}


\author{梁婧 \\ 信息与计算科学，3210105193}

\begin{document}

\maketitle

\section{BSTSorting函数的实现}  
\subsection {排序算法}
  排序算法的实现方式将传入数组的数据依次插入树中，实现排序。然后将树中缓存的数据从小到大依次插入新的数组。最后将新老数组的内容交换。

\subsection{打乱算法}
打乱算法的伪代码如下


\begin{shaded}
\begin{verbatim}
  for (int i = 0; i < arr.size; i++)
    {
    int r = i + rand() % ( arr.size - i);
    swap( arr[i], arr[r]);
    }
\end{verbatim}
\end{shaded}
遍历整个数组，在遍历的过程中交换当前元素和数组中随机一个元素，从而实现数组打乱。


\section{BinarySearchTree 的部分修改}
给 BinaryNode 结构添加了 Number 属性，用于存储每一个节点中的数据个数，从而实现在树中存储重复的数据。避免数组中重复的数字在输入树时丢失。
同时为了保证程序的逻辑其当，适当修改了printTree、insert、remove、clone函数的内容。

\section{main.cpp 测试程序}
测试程序运行的过程中，有三种生成数组的方式\\
(1)随机生成一个给定长度的数组\\
(2)生成一个给定长度的从大到小的数组，即最坏情况下的数组\\
(3)手动输入数组


之后可以选择是否打乱数组以及是否需要查看被打乱的数组、排序之后的数组。\\
然后会由 “ time: ” 的形式给出本次操作花费的时间。


\section{测试记录}
改变数组长度和数据情况、数组打乱与否，可以得到多组测试结果。汇总为如下表格：

\begin{table}[htbp]
  \caption{时间}
  \centering
\scalebox{1.5}{
\renewcommand\arraystretch{1}{
\setlength{\tabcolsep}{5mm}{
\begin{tabular}{|p{2cm}<{\centering}|p{1cm}<{\centering}|p{1cm}<{\centering}|p{1cm}<{\centering}|p{1cm}<{\centering}|}
  \hline
  \diagbox[innerwidth=2cm]{情景}{time}{长度} & 3000&5000&7000&9000\\
\hline
随机不打乱 & 631 & 999 & 1487 & 1985 \\
\hline
随机打乱 & 718 & 1033 & 1578 & 2924\\
\hline
最差不打乱 & 66774 & 190083 & 383625 & 639382\\
\hline
最差打乱 & 668 & 1456 & 1951 & 2288\\
\hline
\end{tabular}}}}
\end{table}




\section{内存泄露检查}
利用如下指令进行内存泄漏检查
\begin{shaded}
\begin{verbatim}
    g++ -g main.cpp
    valgring ./a.cout
\end{verbatim}  
\end{shaded}
使用测试案例输入输出如下
\begin{shaded}
\begin{verbatim}
请输入想要测试的情况。
0 为随机生成的测试数组，代表普遍情况, 1 为最坏的情况. 2 为自定义数组 
0

输入数组的长度。请勿输入整数以外的数据！
500

请输入数据的排序模式。1表示需要打乱后再排序。0表示不需要打乱直接排序
1

将数组打乱
要不要输出乱顺序数组? 要就扣1,不要扣0.
0

需要查看排序后的数组吗？需要输入1，不需要输入0
0
time:9766

是否重新开始测试？如果是，请输入1.如果结束程序，请输入0.
0
再见
==31878== 
==31878== HEAP SUMMARY:
==31878==     in use at exit: 0 bytes in 0 blocks
==31878==   total heap usage: 123 allocs, 123 frees, 86,136 bytes allocated
==31878== 
==31878== All heap blocks were freed -- no leaks are possible
==31878== 
==31878== For lists of detected and suppressed errors, rerun with: -s
==31878== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

\end{verbatim}  
\end{shaded}
经检查，无内存泄漏发生。
\end{document}
